package cn.hesion.dataStructures.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Graph {
    //保存节点值的数组
    private List<String> vertexList;
    //用于保存两个节点的邻接关系的矩阵
    private int[][] edges;
    private int numOfEdges; //表示边的数目
    //保存该节点访问状态的数组
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String[] vertexs = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(n);
        for (int i = 0; i < vertexs.length; i++) {
            graph.insertVertx(vertexs[i]);
        }
        //添加边
        //A-B A-C B-C B-D B-E
        graph.insertEdge(0, 1, 1); // A-B
        graph.insertEdge(0, 2, 1); //
        graph.insertEdge(1, 2, 1); //
        graph.insertEdge(1, 3, 1); //
        graph.insertEdge(1, 4, 1); //

        graph.showGrap();
        System.out.println("深度优先");
        graph.dfs();
        System.out.println();
        System.out.println("广度优先");
        graph.bfs();
    }

    //构造器，做初始化的工作
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>();
        numOfEdges = 0;
    }

    //向外提供一个边数量的函数
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //添加节点
    public void insertVertx(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     表示点的下标即第几个顶点
     * @param v2     第二个顶点对应的下标
     * @param weight 表示这两个顶点的连接关系
     */
    public void insertEdge(int v1, int v2, int weight) {
        //两个顶点有了关系就是双向的，因此两个坐标的值都得置为weight
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        //将边的数量++
        numOfEdges++;
    }

    //向外提供展示边的邻接矩阵的方法
    public void showGrap() {
        for (int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    //深度优先遍历
    //先封装两个方法
    //1获取第一个邻接的节点的坐标
    public int getFirstNeighbor(int index) {
        //循环遍历节点数组
        //遍历出的每个节点的坐标和当前传入的节点坐标带入邻接矩阵
        //找到对应坐标的值不为0 的的第一个数，返回
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    //2获取前一个节点的下一个节点

    /**
     * 获取下一个邻接节点
     *
     * @param v1 告诉函数谁的邻接节点
     * @param v2 告诉之前遍历到的节点
     * @return
     */
    public int getNextNebior(int v1, int v2) {
        for (int i = v2 + 1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    // 根据节点的坐标，输出节点值
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //由于每个节点都要遍历因此需要重载dfs方法，通过循环改变传入的参数
    public void dfs() {
        //需要对isVisited初始化
        isVisited = new boolean[vertexList.size()];

        for (int i = 0; i < getNumofVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    private int getNumofVertex() {
        return vertexList.size();
    }

    /**
     * DeepFirstSearch深度优先遍历
     *
     * @param isVisited 传入数组，该数组记录了该节点有无被遍历
     * @param i         需要开始遍历的节点。
     */
    public void dfs(boolean[] isVisited, int i) {
        //遍历到该节点即输出
        System.out.print(getValueByIndex(i) + "=>");
        //输出完不要忘记告诉isVisited数组，该坐标的节点已经被遍历了
        isVisited[i] = true;
        //寻找该坐标节点的第一个邻接节点
        int w = getFirstNeighbor(i);
        //开始访问便利，直到w变为-1 即遍历的那个阶段和接下来的节点没有关联关系为止
        while (w != -1) {
            //判断该节点是否被访问过
            if (!isVisited[w]) {
                //没有被遍历到
                //由于接下来要做的事和本函数的事一样，产生了递归，传入刚获取到
                //的邻接节点的坐标
                dfs(isVisited, w);
            }
            //如果该节点已经被访问了
            //则继续获取下一个邻接节点
            w = getNextNebior(i, w);
        }
    }

    public void bfs() {
        //初始化isVisited数组
        isVisited = new boolean[vertexList.size()];
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

    /**
     * BFS广度优先
     *
     * @param isVisited 传入数组，该数组记录了该节点有无被遍历
     * @param i         要开始遍历的节点。
     */
    public void bfs(boolean[] isVisited, int i) {
        int u = 0; //记录了上一次访问的节点
        int w = 0; //准备要访问的邻接节点
        //用于记录访问顺序的队列
        LinkedList<Integer> queue = new LinkedList<>();
        //输出当前节点
        System.out.print(getValueByIndex(i) + "=>");
        //将当前节点记为已访问
        isVisited[i] = true;
        //将该节点放入queue中
        queue.addLast(i);
        while (!queue.isEmpty()) {
            //从queue中取出
            u = queue.removeFirst();
            //获取该节点的第一个邻接节点
            w = getFirstNeighbor(u);
            //拿到该邻接节点开始从该节点去遍历
            while (w != -1) {
                //先判断有没有访问过
                if (!isVisited[w]) {
                    //该节点没有被访问过，则进行访问，输出该节点
                    System.out.print(getValueByIndex(w) + "=>");
                    //将该节点置为已访问
                    isVisited[w] = true;
                    //将该节点访问queue的队尾
                    queue.addLast(w);
                }
                //访问结束，开始访问下一个节点
                w = getNextNebior(u, w);
            }
        }
    }

}
